/*
 * Graph_dfs.cpp
 *
 *  Created on: 31.03.2014
 *      Author: Medvedeva Anna
 */

#include <list>
#include <stack>
#include <deque>
#include <vector>
#include <iostream>
#include "Graph.h"

using namespace std ;

void Graph::dfs()
{
	cout << "DFS:\n";
	vector <int> colorsVertices(numbVertices,0); 						//0 - white, 1- grey, 2- black
	stack <pair < int,int > > dfsVertices;
	for (int i = 0; i < numbVertices; i++) {
		if (colorsVertices[i] == 0)
			dfs(i, colorsVertices);
	}
	cout << endl;
}

int Graph::dfs(int vertex, vector <pair <int,int> > &infoVertices, pair<int,int> (*after_stack)(int, int))
{
	int cycle = 0;
	vector <int> colorsVertices(numbVertices,0); 						//0 - white, 1- grey, 2- black
	int time = 0;
	stack <pair < int,int > > dfsVertices;
	cycle = dfs(vertex,time ,colorsVertices, infoVertices, after_stack);
	for (int i = 0; i < numbVertices; i++) {
		if (colorsVertices[i] == 0) {
			cycle+=dfs(i, time, colorsVertices, infoVertices, after_stack);
		}
	}
	return cycle;
}

int Graph::dfs(int vertex,int &time, vector<int> &colorsVertices,vector <pair <int,int> > &infoVertices, pair<int,int> (*after_stack)(int, int))
{
	int cycle = 0;
	stack <int> dfsVertices;
	make_grey(colorsVertices,vertex);
	dfsVertices.push(vertex);
	while (!dfsVertices.empty()) {
		int curVertex = dfsVertices.top();
		dfsVertices.pop();

		cycle+= add_neighbors(curVertex, colorsVertices, dfsVertices);
		make_black(colorsVertices, curVertex);
		infoVertices[curVertex] = (*after_stack)(curVertex,time);
		time++;
	}
	return cycle;
}

void Graph::dfs(int vertex, vector<int> &colorsVertices)
{
	stack <int> dfsVertices;

	make_grey(colorsVertices,vertex);
	dfsVertices.push(vertex);
	while (!dfsVertices.empty()) {
		int curVertex = dfsVertices.top();
		dfsVertices.pop();
		cout << curVertex + 1 << " ";
		add_neighbors(curVertex, colorsVertices, dfsVertices);
		make_black(colorsVertices, curVertex);
	}
	//cout << endl;
}

int Graph::add_neighbors (int vertex, vector<int> &colors, stack <int > &dfsVertices)
{
	int cycle = 0;
	if (list_edges.empty()) {
		for (int i = 0 ; i < numbVertices; i++) {
			if (connect_matrix[vertex][i]) {
				if (colors[i] == 0) {
					make_grey(colors, i);
					dfsVertices.push(i);
				} else if (colors[i] == 1){
					cycle = 1;
				}
			}
		}
	} else {
		list<int>::iterator i = list_edges[vertex].begin();
		while(i != list_edges[vertex].end()){
			int curVert = *i;
			if (colors[curVert] == 0) {
				make_grey(colors, curVert);
				dfsVertices.push(curVert);
			} else if (colors[curVert] == 1){
				cycle = 1;
			}
			i++;
		}
	}
	return cycle;
}

